#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head->next == nullptr)
        {
            return head;
        }
        ListNode dummy(0);
        ListNode* dhead = new ListNode(0);
        dhead->next = head;
        ListNode* cur = head;

        while (cur)
        {
            ListNode* prev = dhead;
            while (prev->next != nullptr && prev->next->val < cur->val)
            {
                prev = prev->next;
            }
            ListNode* cNext = cur->next;
            cur->next = prev->next;
            prev->next = cur;
            cur = cNext;
            prev = dhead;
        }
        return dhead->next;
    }
};